import java.util.Arrays;

public class Solution628 {
    public int maximumProduct(int[] nums) {
        int[] pos=new int[3];
        Arrays.fill(pos,-1);
        int[] neg=new int[2];
        for (int i=0;i<nums.length;i++){
            if (nums[i]<0){
                if (nums[i]<neg[0]){
                    neg[1]=neg[0];
                    neg[0]=nums[i];
                }else if (nums[i]<neg[1]){
                    neg[1]=nums[i];
                }
            }else{
                if (nums[i]>pos[0]){
                    pos[2]=pos[1];
                    pos[1]=pos[0];
                    pos[0]=nums[i];
                }else if (nums[i]>pos[1]){
                    pos[2]=pos[1];
                    pos[1]=nums[i];
                }else if (nums[i]>pos[2]){
                    pos[2]=nums[i];
                }
            }
        }
        if (pos[0]==-1){
            neg=new int[3];
            Arrays.fill(neg,Integer.MIN_VALUE);
            for (int i=0;i<nums.length;i++){
                if (nums[i]>neg[0]){
                    neg[2]=neg[1];
                    neg[1]=neg[0];
                    neg[0]=nums[i];
                }else if (nums[i]>neg[1]){
                    neg[2]=neg[1];
                    neg[1]=nums[i];
                }else if (nums[i]>neg[2]){
                    neg[2]=nums[i];
                }
            }
            return neg[0]*neg[1]*neg[2];
        }
        if (pos[2]==-1){
            return neg[0]*neg[1]*pos[0];
        }
        return Math.max(neg[0]*neg[1]*pos[0],pos[0]*pos[1]*pos[2]);
    }

    public static void main(String[] args) {
        System.out.println(new Solution628().maximumProduct(new int[]{1,2,3}));
    }
}
